package org.paradac.examples.quicksort.main;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.LineNumberReader;
import java.util.ArrayList;
import java.util.Random;

import org.paradac.DivideAndConquer;
import org.paradac.INodeProcessor;

public class Quicksort {

	public static void debug(Object o) {
		System.out.println("DEBUG: " + o);
	}

	// generates n random number
	public static ArrayList<Double> randomNumberGen(int n) {
		Random r = new Random(System.currentTimeMillis());
		ArrayList<Double> rNums = new ArrayList<Double>(n);
		for (int i = 0; i < n; i++) {
			rNums.add(r.nextDouble());
		}
		return rNums;
	}

	// generates n random number
	public static ArrayList<Double> randomNumberGenGaussian(int n) {
		Random r = new Random(System.currentTimeMillis());
		ArrayList<Double> rNums = new ArrayList<Double>(n);
		for (int i = 0; i < n; i++) {
			rNums.add(r.nextGaussian());
		}
		return rNums;
	}

	public static void quicksort(ArrayList<Double> a) {
//		shuffle(a); // to guard against worst-case
		quicksort(a, 0, a.size() - 1);
	}

	// quicksort a[left] to a[right]
	public static void quicksort(ArrayList<Double> a, int left, int right) {
		if (right <= left)
			return;
		int i = partition(a, left, right);
		quicksort(a, left, i - 1);
		quicksort(a, i + 1, right);
	}

	private static int partition(ArrayList<Double> a, int left, int right) {
		int i = left - 1;
		int j = right;
		while (true) {
			while (less(a.get(++i), a.get(right)))
				// find item on left to swap
				; // a[right] acts as sentinel
			while (less(a.get(right), a.get(--j)))
				// find item on right to swap
				if (j == left)
					break; // don't go out-of-bounds
			if (i >= j)
				break; // check if pointers cross
			exch(a, i, j); // swap two elements into place
		}
		exch(a, i, right); // swap with partition element
		return i;
	}

	private static boolean less(double x, double y) {
		comparisons++;
		return (x < y);
	}

	private static long comparisons = 0;
	private static long exchanges = 0;

	// exchange a[i] and a[j]
	private static void exch(ArrayList<Double> a, int i, int j) {
		exchanges++;
		double swap = a.get(i);
		a.set(i, a.get(j));
		a.set(j, swap);
	}

	// shuffle the array a[]
	public static void shuffle(ArrayList<Double> a) {
		int N = a.size();
		for (int i = 0; i < N; i++) {
			int r = i + (int) (Math.random() * (N - i)); // between i and N-1
			exch(a, i, r);
		}
	}

	public static class QSTreeNodeProcessor implements INodeProcessor<TreeNodeData> {
		public void conqueror(DivideAndConquer<TreeNodeData> tree, TreeNodeData treeNode) {
		}

		public Boolean isLeaf(TreeNodeData t) {
			return t.right <= t.left;
		}

		public ArrayList<TreeNodeData> divider(TreeNodeData node) {
			if (node.right <= node.left)
				return new ArrayList<TreeNodeData>(0);
			int pivot = partition(node.data, node.left, node.right);
			ArrayList<TreeNodeData> children = new ArrayList<TreeNodeData>(2);
			children.add(new TreeNodeData(node.data, node.left, pivot - 1));
			children.add(new TreeNodeData(node.data, pivot + 1, node.right));
			return children;
		}
	}

	public static ArrayList<Double> readNums(String filename) {
		ArrayList<Double> data = new ArrayList<Double>();
		try {
			LineNumberReader lineNumberReader = new LineNumberReader(new InputStreamReader(
			    new FileInputStream(new File(filename))));
			String l = lineNumberReader.readLine();
			while (l != null) {
				data.add(Double.valueOf(l));
				l = lineNumberReader.readLine();
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return data;
	}

	public static void run(String args[]) {
		ArrayList<Double> data = new ArrayList<Double>();
		data = readNums(args[0]);
		System.out.println("Sorting " + data.size() + " items ...");
		long runtime = System.currentTimeMillis();
		TreeNodeData root = new TreeNodeData(data, 0, data.size() - 1);
		DivideAndConquer<TreeNodeData> tree = new DivideAndConquer<TreeNodeData>(root,
		    new QSTreeNodeProcessor());
		tree.divide();
		// /*
		runtime = System.currentTimeMillis() - runtime;
		System.out.println("M:runtime: " + runtime + " ms");
		
		data = readNums(args[0]);
		runtime = System.currentTimeMillis();
		quicksort(data);
		runtime = System.currentTimeMillis() - runtime;
		System.out.println("S:runtime: " + runtime + " ms");
		
		Double old = Double.NEGATIVE_INFINITY;
		for (Double d : data) {
			if (d < old) {
				debug("INCORRECT RESULT!");
			}
			old = d;
		}
	}

	public static void main(String[] args) {
		run(args);
	}

}
